#
# @lc app=leetcode.cn id=42 lang=python
#
# [42] 接雨水
#

# @lc code=start
class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        stack = []
        result = 0
        for i in range(len(height)):
            while stack and height[i]>0:
                if i-stack[-1] > 1:
                    temp = max(height[stack[-1]+1 : i])
                else:
                    temp = 0

                result += (i-stack[-1]-1)*(min(height[i], height[stack[-1]])-temp)
                if height[i] >= height[stack[-1]]:
                    stack.pop()
                else:
                    break 
            if height[i] > 0:
                stack.append(i)
        return result
                
        
# @lc code=end

